#include <stdio.h>
#include <stdlib.h>

/*
 * 带权路径长度达到最小，称这样的二叉树为最优二叉树，也称哈夫曼树 (Huffman tree)
 */

#define max_leaf 8	/* 叶子数目 */
#define keshu    ((2*max_leaf) - 1) /* 森林中树的棵树 */

/* 采用双亲孩子法存储 */
struct tree 
{
  int weight;
  int parent;
  int lchild;
  int rchild;
};

struct tree  hftree[keshu + 1];

void huffman()
{
  int i, j, p1, p2;
  int s1, s2;

  for (i = 1; i <= keshu; i++) {
    hftree[i].parent = 0;
    hftree[i].lchild = 0;
    hftree[i].rchild = 0;
    hftree[i].weight = 0;
  }

  for (i = 1; i <= max_leaf; i++) {
    scanf("%d", &hftree[i].weight);
  }

  for (i = max_leaf + 1; i <= keshu; i++) {  /* 进行n-1次合并 */
    p1 = 0;	// p1, p2 分别指向两个权值最小的值的位置
    p2 = 0;
    s1 = s2 = 32767;	// 代表两个最小权值

    for (j = 1; j <= i - 1; j++)	// 选两个最小值
      if (hftree[j].parent == 0)	// 该权值还没有被选中
	if (hftree[j].weight < s1) {
	  s2 = s1;
	  s1 = hftree[j].weight;
	  p2 = p1;
	  p1 = j;
	}
	else if (hftree[j].weight < s2) {
	  s2 = hftree[j].weight;
	  p2 = j;
	}

    hftree[p1].parent = i;	// 以下为合并
    hftree[p2].parent = i;
    hftree[i].lchild = p1;
    hftree[i].rchild = p2;
    hftree[i].weight = hftree[p1].weight + hftree[p2].weight;
  }

  printf("i : weight : parent : lchild : rchild \n");
  for (i = 1; i <= keshu; i++)
    printf(" %d\t %d\t %d\t %d\t %d\n", i, hftree[i].weight, hftree[i].parent, hftree[i].lchild, hftree[i].rchild);
}

void main()
{
  huffman();
}
